package com.topcoder.srm514;

public class MagicalGirlLevelThreeDivTwo {
	private long		MAX = 1000000000000001L;
	private int 		K;
	private int 		N;
	private long[]		len;
	private int[][]		ck;
	
	public int theCount(String[] first, int n, long lo, long hi) {
		K = first.length;
		N = Math.max(n, K);
		len = new long[N+1];
		ck = new int[K][51];
		
		for (int i=0; i<K; i++) {
			len[i] = first[i].length();
			for (int j=0; j<len[i]; j++) {
				ck[i][j+1] = ck[i][j] + (first[i].charAt(j) == '1'? 1 : 0);
			}
		}
		
		for (int i=K; i<=N; i++) {
			len[i] = Math.min(len[i-1] + len[i-K], MAX);
		}

		return count(n, lo, hi);
	}
	
	private int count(int i, long start, long end) {
		if (i < K) return ck[i][(int)end+1] - ck[i][(int)start];

		if (start >= len[i-1]) return count(i-K, start-len[i-1], end-len[i-1]);
		if (end < len[i-1]) return count(i-1, start, end);
		return count(i-1, start, len[i-1]-1) + count(i-K, 0, end-len[i-1]);
	}
}
